package com.love;

import javax.swing.tree.TreeNode;

/**
 * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 */
public class TreeConst {



    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

       public TreeNode(int val){
            this.val = val;
        }

    }


    public static TreeNode buildTree (int[] preTree,int[] inTree){
        if(preTree == null || inTree == null || preTree.length != inTree.length){
            return null;
        }
        return getTree(preTree,0,preTree.length -1,inTree,0,inTree.length -1);


    }

    /**
     * 有一棵树, 先序结果是 pre[L1...R1], 中序结果是 in[L2...R2]
     * @param preTree
     * @param L1
     * @param R1
     * @param inTree
     * @param L2
     * @param R2
     * @return 建出整棵树，返回头节点
     */
    public static TreeNode getTree(int[] preTree,int L1,int R1,int[] inTree,int L2,int R2){
        if(L1 > R1){
            return null;
        }
        TreeNode head = new TreeNode(preTree[L1]);
        if(L1 == R1){
            return head;
        }
        int find = L2;
        while (inTree[find] != preTree[L1]){
            find++;
        }
        head.left = getTree(preTree,L1 + 1,L1 + (find - L2),inTree,L2,find);
        head.right = getTree(preTree,L1 + (find - L2) + 1,R1,inTree,find + 1,R2);


        return head;



    }



}
